package leetcode_900;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *UniqueLetterString_828 给定一个字符串 问其所有子串里不重复的字符个数和是多少
 *describe:非常有技巧 只需要遍历每个字符出现的index AC 24%
 *see:https://leetcode.com/articles/unique-letter-string/
 *2018年10月30日 下午2:50:40
 */
public class UniqueLetterString_828_ {
	public int uniqueLetterString(String S) {
        Map<Character,List<Integer>> map=new HashMap<Character,List<Integer>>();
        char []chars=S.toCharArray();
        for(int i=0;i<chars.length;++i) {
        	map.computeIfAbsent(chars[i], x->new ArrayList<Integer>()).add(i);
        }
        long res=0;
        for(List<Integer> list:map.values()) {
        	for(int i=0;i<list.size();++i) {//遍历每个字符集的Index
        		long left=i==0?-1:list.get(i-1);
        		long right=i==list.size()-1?S.length():list.get(i+1);
        		res+=(list.get(i)-left)*(right-list.get(i));
        	}
        }
        return (int) res % 1_000_000_007;
    }
}
